package algotithm.leetcode.slidingwindow.test239;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/29-22:55
 * @Title 239. 滑动窗口最大值
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        Solution solution = new Solution();
        int[] arr = solution.maxSlidingWindow(nums,k);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || k < 0) {
            return new int[]{0};
        }
        Deque<Integer> deque = new ArrayDeque<>();
        int[] arr = new int[n - k + 1];
        for (int i = 0 ; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }
        arr[0] = deque.peekFirst();
        for (int i = k; i < n; i++) {
            if (nums[i - k] == deque.getFirst()) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            arr[i - k + 1] = deque.getFirst();
        }
        return arr;
    }
}